1. Field of the Invention
The present invention relates to a decoding method and a decoding apparatus that are applicable to a circuit and a program storage medium for achieving an error correction coding technology using an algebraic technique, for example.
2. Description of the Related Art
For algebraic geometric codes, such as Reed-Solomon codes and BCH codes, which are subfield subcodes of the Reed-Solomon codes, high-performance and low-computational cost decoding methods employing their algebraic properties are known.
Suppose, for example, that a Reed-Solomon code having a code length n, an information length k, a field of definition GF(q) (q=pm, p: a prime number), and a minimum distance d=n−k is denoted as RS(n, k). It is well known that minimum distance decoding (common decoding) of decoding a hard decision reception word into a codeword having a minimum Hamming distance guarantees correction of t (t<d/2) erroneous symbols.
Guruswami-Sudan list decoding (hereinafter referred to as “G-S list decoding”) guarantees correction of t (t<√nk) erroneous symbols (see V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon and Algebraic-Geometry codes, IEEE Transactions on Information Theory, vol. 45, pp. 1757-1767, 1999).
Koetter-Vardy list decoding (hereinafter referred to as “K-V list decoding”), which is an extended version of the Guruswami-Sudan list decoding and uses a soft decision reception word, is, as with the Guruswami-Sudan list decoding, made up of the following four steps: (1) calculation of reliability of each symbol from received information; (2) extraction of two-variable polynomial interpolation conditions from the reliability; (3) interpolation of two-variable polynomials; and (4) factorization of interpolation polynomials and creation of a list of decoded words. It is known that the K-V list decoding has higher performance compared to when hard decision decoding is applied (see R. Koetter and A. Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory, 2001).
It is also known that computational cost thereof can be reduced to a practical level by re-encoding (see R. Koetter, J. Ma, A. Vardy, and A. Ahmed, Efficient Interpolation and Factorization in Algebraic Soft-Decision Decoding of Reed-Solomon codes, Proceedings of ISIT 2003).
As to linear codes, low-density parity-check codes (LDPC codes) capable of achieving high performance, nearly marginal performance, through iterative decoding using belief propagation (BP) have been recently attracting attention (see D. MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory, 1999).
It is theoretically known that the belief propagation (BP) used in the LDPC codes is generally effective only for linear codes having a low-density parity-check matrix. Also, it is known that reducing the density of a parity-check matrix of the Reed-Solomon codes or the BCH codes is NP-hard (see Berlekamp, R. McEliece, and H. van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, vol. 24, pp. 384-386, May, 1978).
Thus, it has been considered difficult to apply the belief propagation (BP) to the Reed-Solomon codes or the BCH codes.
However, in 2004, Narayanan et al. suggested that application of the belief propagation (BP) to the Reed-Solomon codes, the BCH codes, or linear codes having a parity-check matrix that is not low in density using a parity-check matrix as diagonalized in accordance with the reliability of a reception word is effective (see Jing Jiang and K. R. Narayanan, Soft Decision Decoding of RS Codes Using Adaptive Parity Check Matrices, Proceeding of IEEE International Symposium on Information Theory 2004).
This technique is called adaptive belief propagation (ABP) decoding.
FIG. 1 is a flowchart illustrating ABP decoding proposed.
At step ST1, a reliability order of the reception word is investigated, and at step ST2, order conversion is performed.
At step ST3, a parity-check matrix is diagonalized in accordance with the converted order, and at step ST4, the belief propagation (BP) is performed using the resulting parity-check matrix.
Next, LLR is calculated at step ST5, a reliability order of the calculated LLR is investigated at step ST6, and decoding is performed at step ST7.
Thereafter, the above procedure is performed iteratively until iterative decoding termination conditions SC1 and SC2 are satisfied at steps ST8 and ST9.
When performing iterative decoding using the reliability updated by ABP, a list of decoded word candidates (i.e., candidates for a decoded word) obtained during the process is held, and one of the candidates that is closest to the reception word is finally selected, as the decoded word, from the list of the decoded word candidates. It is known that the probability of occurrence of a decoder error is thus reduced by ABP decoding, resulting in high decoding performance.